package algotithm.weekendrace.leetcode232.test4;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/14-15:20
 */
class Solution {
    public int maximumScore(int[] nums, int k) {
        int length = nums.length;
        int[] left = new int[length];
        int[] right = new int[length];
        Arrays.fill(right, length);
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                right[stack.pop()] = i;
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        int area = 0;
        for (int i = 0; i < length; i++) {
            if (right[i] > k && left[i] < k) {
                area = Math.max(area, (right[i] - left[i] - 1) * nums[i]);
            }
        }
        return area;
    }
}
